#
# @lc app=leetcode.cn id=122 lang=python
#
# [122] 买卖股票的最佳时机 II
#

# @lc code=start
# 贪心算法
# class Solution(object):
#     def maxProfit(self, prices):
#         """
#         :type prices: List[int]
#         :rtype: int
#         """
#         profit = 0
#         for i in range(1, len(prices)):
#             profit += max(prices[i]-prices[i-1], 0)
#         return profit

# 动规
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        dp = [0] * 2
        dp[0] = prices[0]
        dp[1] = 0
    
        for i in range(1, len(prices)):
             dp[1] += max(0, prices[i]-dp[0])
             dp[0] = prices[i]

        return dp[1]



# @lc code=end

